Levenshtein
Implements the Levenshtein distance (Levenshtein, 1966), or edit distance, between two words is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into the other.
It is always at least the difference of the sizes of the two strings.
It is at most the length of the longer string.
It is zero if and only if the strings are equal.
If the strings are the same size, the Hamming distance is an upper bound on the Levenshtein distance.
The Levenshtein distance obeys the triangle inequality (the distance between two strings is no greater than the sum Levenshtein distances from a third string), so it is a metric distance.
The similarity is computed as \(\frac{w_d \lvert X \rvert + w_i \lvert Y \rvert - distance(X, Y)}{2}\).
Note: Because this class currently implements the dynamic programming approach, it has a space requirement \(O(m \times n)\)
References
Levenshtein, V. I. (1966-02). Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, 10, 707-710.
Author
solonovamax
Parameters
The weight of an insertion. Represented as \(w_i\). Must be in the range \([0, 1 \times 10^{10} ]\).
The weight of a deletion. Represented as \(w_d\). Must be in the range \([0, 1 \times 10^{10} ]\).
The weight of a substitution. Represented as \(w_s\). Must be in the range \([0, 1 \times 10^{10} ]\).